﻿using System;
using System.Collections.Generic;
using System.Linq;
using MLSharp.Utilities;

namespace MLSharp.Clustering
{
	/// <summary>
	/// A basic implementation of Knowledge Frontier Discovery (KFD).
	/// </summary>
	/// <remarks>
	/// KFD looks for 'knowledge frontiers' in cluster trees.  It does this by examining the 
	/// nodes in the tree combined with information about the predictive accuracy of a machine
	/// learning technique on each instance in the tree.
	/// </remarks>
	public class KnowledgeFrontierDiscovery
	{
		#region Logger

		/// <summary>
		/// The logger for the type.
		/// </summary>
		private static readonly log4net.ILog mLogger =
			log4net.LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);

		#endregion

		#region Public Const/Readonly fields.

		/// <summary>
		/// The default value for the alpha parameter.
		/// </summary>
		public static readonly double DefaultAlpha = 0.01;

		#endregion

		#region Private Fields

		/// <summary>
		/// The knowledge frontiers that are discovered by the KFD process.
		/// </summary>
		private IList<IKnowledgeFrontier> mKnowledgeFrontiers;

		/// <summary>
		/// The index of the attribute that holds the accuracy value for each instance.
		/// </summary>
		private int mAccuracyIndex;

		#endregion

		#region Public Properties

		/// <summary>
		/// The alpha parameter for cost-complexity pruning.  A value of zero will disable pruning,
		/// while larger values will result in more pruning.
		/// </summary>
		/// <value>The default is 0.01.  This value works well when accuracy is represented in the 
		/// range [0,1].</value>
		public double Alpha { get; set; }

		#endregion

		#region Public Constructors

		/// <summary>
		/// Initializes a new instance.
		/// </summary>
		public KnowledgeFrontierDiscovery()
		{
			Alpha = DefaultAlpha;
		}

		#endregion

		#region Private Methods

		/// <summary>
		/// Recursively (depth-first) checks whether any children of the specified node are
		/// knowledge frontiers.
		/// </summary>
		/// <param name="node">The node whose children will be checked.</param>
		private bool ChildrenArePruneable(IClusterNode node)
		{
			//Perform a depth-first search of the children, and track which are/aren't pruneable. 
			//If a child is not pruneable, that means it contains a knowledge frontier somewhere within it, so the 
			//siblings of that node must become knowledge frontiers themselves.  

			//This flag is set to false if any child is not pruneable.  
			bool nodePruneable = true;

			//And this holds flags for each child to track which are/aren't pruneable.
			bool[] childPruneable = new bool[node.Children.Count];

			//Recursively check each child.
			for (int i=0; i < node.Children.Count; i++)
			{
				childPruneable[i] = ChildrenArePruneable(node.Children[i]);

				if (!childPruneable[i])
				{
					nodePruneable = false;
				}
			}

			//If we can still prune the node, compare it to all the child nodes.
			if (nodePruneable && node.Children.Count > 0)
			{
				//Get aggregate stats for the current node's statistics.
				Stats myStats = GetNodeStats(node);

				//Calculate the cost-complexity if we do prune the children.
				double prunedComplexity = GetResidualSquaredError(myStats, node) + Alpha;

				//And calculate the cost-complexity if we do not prune the children.
				double unprunedComplexity = Alpha*(node.Children.Count); 

				for (int i=0; i < node.Children.Count; i++)
				{
					Stats childStats = GetNodeStats(node.Children[i]);

					unprunedComplexity += GetResidualSquaredError(childStats, node.Children[i]);
				}

				if (mLogger.IsDebugEnabled)
				{
					mLogger.DebugFormat("Pruned complexity: {0}, unpruned complexity: {1}", prunedComplexity, unprunedComplexity);
				}

				//If the cost-complexity is lower for the unpruned tree, don't prune, otherwise, prune
				if (unprunedComplexity < prunedComplexity)
				{
					if (mLogger.IsDebugEnabled)
					{
						mLogger.DebugFormat("Subtrees cannot be pruned further.");
					}

					nodePruneable = false;
				}
			}

			//If any node was not pruneable, the remaining nodes must become knowledge frontiers
			if (!nodePruneable)
			{
				for (int i = 0; i < node.Children.Count; i++)
				{
					//If the child wasn't pruneable, it already has a knowledge frontier within it.
					if (childPruneable[i])
					{
						Stats childStats = GetNodeStats(node.Children[i]);
						mKnowledgeFrontiers.Add(new KnowledgeFrontier(node.Children[i], childStats.Mean, childStats.StdDev));
					}
				}
			}

			return nodePruneable;
		}

		/// <summary>
		/// Calculates the residual squared error of the accuracy of the specified node.
		/// </summary>
		/// <param name="nodeStats"></param>
		/// <param name="node"></param>
		/// <returns></returns>
		private double GetResidualSquaredError(Stats nodeStats, IClusterNode node)
		{
			double residualSquaredError = 0;

			foreach (Instance instance in node.Instances)
			{
				residualSquaredError += Math.Pow(nodeStats.Mean - instance.Values[mAccuracyIndex], 2);
			}

			//return residualSquaredError;
			return residualSquaredError / node.Instances.Count;
		}

		/// <summary>
		/// Gets the accuracy stats for the specified node.
		/// </summary>
		/// <param name="clusterNode"></param>
		/// <returns></returns>
		private Stats GetNodeStats(IClusterNode clusterNode)
		{
			Stats stats = new Stats();

			foreach (Instance instance in clusterNode.Instances)
			{
				stats.Add(instance.Values[mAccuracyIndex]);
			}

			stats.CalculateDerived();

			return stats;
		}

		#endregion

		#region Public Methods

		/// <summary>
		/// Finds knowledge frontiers in the specified tree that was created from instances
		/// in the specified <paramref name="dataSet"/>.
		/// </summary>
		/// <param name="root">The root node.</param>
		/// <param name="dataSet">The corresponding dataset.</param>
		/// <returns>
		/// The identified knowledge frontiers.
		/// </returns>
		public IKnowledgeFrontier[] FindFrontiers(IClusterNode root, IDataSet dataSet)
		{
			//Find the index of the accuracy attribute.
			mAccuracyIndex = dataSet.Attributes.FindIndex(a => a.Name == "Accuracy");

			//If the attribute couldn't be found
			if (mAccuracyIndex < 0)
			{
				throw new ArgumentException("Dataset doesn't contain an attribute named 'Accuracy'.", "dataSet");
			}

			//Perform a depth-first traversal of the tree
			mKnowledgeFrontiers = new List<IKnowledgeFrontier>();

			//See if the tree contains any frontiers
			if (ChildrenArePruneable(root))
			{
				//If all children of the root are pruneable, the root is our frontier, so create the frontier node.
				Stats stats = GetNodeStats(root);
				mKnowledgeFrontiers.Add(new KnowledgeFrontier(root, stats.Mean, stats.StdDev));				
			}

			//Don't hold a reference to anything as it will eat up memory.
			IKnowledgeFrontier[] result = mKnowledgeFrontiers.ToArray();
			mKnowledgeFrontiers = null;

			return result;
		}

		#endregion
	}
}
